The problem of adequately testing digital logic circuits has grown substantially more complex over the years with the rapid increase in the complexity of the logic circuits being designed and fabricated. Most modem approaches to this problem involve the use of automatic test generation (ATG) systems which are charged with the task of automatically generating a comprehensive test plan for a given circuit design. Such an ATG system is provided with a description of the circuit design, typically in terms of its constituent circuit elements (e.g., logic gates) and the interconnections among those elements and to the circuit's primary inputs and primary outputs. The ATG system then automatically generates circuit stimuli which, when applied to the primary inputs of a fabricated instance of the given circuit design, will result in a response at the circuit's primary outputs which will identify (with a reasonable degree of certainty) whether the fabricated circuit is operating in accordance with the given circuit design.
Since the number of possible malfunctions which a fabricated circuit may theoretically exhibit is extremely large, ATG systems typically perform their task (and measure the quality of their result) based on a fault "model" in which only a comparatively small number of possible malfunctions are considered. The most common such model, the "stuck-at" fault model, enumerates the set of malfunctions in which each circuit lead (i.e., each input to and each output from a circuit element) may be individually "stuck" at one of its possible values (e.g., logic 0 or Logic 1). In this manner, the number of possible faults to be considered is limited to twice the number of circuit leads. The "stuck-at" fault model has become well accepted as providing a reasonable correspondence to the set of likely physical errors which typically result from the fabrication process.
Most ATG systems select one of the modelled faults at a time, and attempt to generate tests (i.e., circuit stimuli) which will be able to "detect" that fault. That is, the system's goal is to find circuit stimuli which, when applied to the primary inputs of a "defective" circuit (i.e., one which has the given fault), will result in a response at the circuit's primary outputs which differs from that of a properly operational circuit. Usually, these circuit stimuli are generated as a result of an exhaustive search procedure involving substantial trial and error. For most typical circuit designs, however, quite a few of the faults may, if actually present in a fabricated instance of the circuit, cause no discernable change in the circuit behavior at all. These faults are, therefore, undetectable or untestable. (In fact, they usually reflect an inherent logic redundancy in the circuit design.) Thus, absent some means of identifying untestable faults, most ATG systems will identity such faults as untestable only after exhausting the search space being examined. Therefore, a large portion of an ATG system's time (if not most of it) may be spent in futile attempts to generate tests for untestable faults.
Although prior art techniques which eliminate some untestable faults have been used, these techniques typically eliminate only a small portion of all untestable faults. In particular, a conventional circuit lead "controllability" and "observability" analysis may be performed to identify circuit leads which either cannot be set to a given logic value (i.e., are uncontrollable to that value), or whose value cannot be observed at the circuit's primary outputs. As a result of such an analysis, a limited number of untestable faults can be identified. However, the identification of the vast majority of untestable faults is not so simple. Most untestable faults occur due to more complex circuit redundancies in which all of the relevant circuit leads are individually controllable to both logic values and are also observable at the circuit's primary outputs.